WIGDERSON, AVI : rechercher sur Z-Library

Noam Nisan, Avi Wigderson

Année:

1999

Langue:

english

Fichier:

PDF, 308 KB

english, 1999

Lower bounds on arithmetic circuits via partial derivatives

Journal:

Omer Reingold, Salil Vadhan and Avi Wigderson

Année:

1996-1997

Langue:

english

Fichier:

PDF, 883 KB

english, 1996-1997

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders

Journal:

Annals of Mathematics

Année:

2002

Langue:

english

Fichier:

PDF, 3.07 MB

english, 2002

[ACM Press the twentieth annual ACM symposium - Chicago, Illinois, United States (1988.05.02-1988.05.04)] Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 - Completeness theorems for non-cryptographic fault-tolerant distributed computation

Ben-Or, Michael, Wigderson, Avi

Année:

1988

Langue:

english

Fichier:

PDF, 1021 KB

english, 1988

Superpolynomial Lower Bounds for Monotone Span Programs

László Babai, Anna Gál, Avi Wigderson

Journal:

Combinatorica

Année:

1999

Langue:

english

Fichier:

PDF, 290 KB

english, 1999

Expander graphs and their applications

Hoory, Shlomo, Linial, Nathan, Wigderson, Avi

Journal:

Bulletin of the American Mathematical Society

Année:

2006

Langue:

english

Fichier:

PDF, 1.58 MB

english, 2006

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Goldreich, Oded, Micali, Silvio, Wigderson, Avi

Journal:

Journal of the ACM

Année:

1991

Langue:

english

Fichier:

PDF, 2.90 MB

english, 1991

Search in a Known Pattern

Motty Perry and Avi Wigderson

Journal:

Journal of Political Economy

Année:

1986

Langue:

english

Fichier:

PDF, 160 KB

english, 1986

Population recovery and partial identification

Wigderson, Avi, Yehudayoff, Amir

Journal:

Machine Learning

Année:

2016

Langue:

english

Fichier:

PDF, 356 KB

english, 2016

[IEEE 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) - Toronto, ON, Canada (1986.10.27-1986.10.29)] 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) - Probabilistic Boolean decision trees and the complexity of evaluating game trees

Saks, Michael, Wigderson, Avi

Année:

1986

Langue:

english

Fichier:

PDF, 1.02 MB

english, 1986

Randomness vs Time: Derandomization under a Uniform Assumption

Russell Impagliazzo, Avi Wigderson

Journal:

Prabhakar Ragde, Avi Wigderson

Année:

2001

Langue:

english

Fichier:

PDF, 182 KB

english, 2001

Linear-size constant-depth polylog-threshold circuits

Journal:

Information Processing Letters

Année:

1991

Langue:

english

Fichier:

PDF, 461 KB

english, 1991

The complexity of parallel search

Richard M. Karp, Eli Upfal, Avi Wigderson

Journal:

Année:

1988

Langue:

english

Fichier:

PDF, 1.80 MB

english, 1988

Derandomized graph products

Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman

Journal:

Joel Friedman, Avi Wigderson

Année:

1995

Langue:

english

Fichier:

PDF, 915 KB

english, 1995

On the second eigenvalue of hypergraphs

Journal:

Combinatorica

Année:

1995

Langue:

english

Fichier:

PDF, 1.08 MB

english, 1995

Rectilinear Graphs and Their Embeddings

Vijayan, Gopalakrishnan, Wigderson, Avi

Journal:

Gil, Joseph, Auf Der Heide, Friedhelm Meyer, Wigderson, Avi

Année:

1985

Langue:

english

Fichier:

PDF, 2.02 MB

english, 1985

The Tree Model for Hashing: Lower and Upper Bounds

Journal:

Ambainis, Andris, Schulman, Leonard J., Ta-Shma, Amnon, Vazirani, Umesh, Wigderson, Avi

Année:

1996

Langue:

english

Fichier:

PDF, 2.59 MB

english, 1996

The Quantum Communication Complexity of Sampling

Journal:

Impagliazzo, Russell, Jaiswal, Ragesh, Kabanets, Valentine, Wigderson, Avi

Année:

2003

Langue:

english

Fichier:

PDF, 219 KB

english, 2003

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized

Journal:

Barak, Boaz, Impagliazzo, Russell, Wigderson, Avi

Année:

2010

Langue:

english

Fichier:

PDF, 400 KB

english, 2010

Extracting Randomness Using Few Independent Sources

Journal:

Shpilka, Amir, Wigderson, Avi

Année:

2006

Langue:

english

Fichier:

PDF, 310 KB

english, 2006

Derandomizing Homomorphism Testing in General Groups

Journal:

Goldreich, Oded, Micali, Silvio, Wigderson, Avi

Année:

2006

Langue:

english

Fichier:

PDF, 202 KB

english, 2006

[IEEE 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) - Toronto, ON, Canada (1986.10.27-1986.10.29)] 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) - Proofs that yield nothing but their validity and a methodology of cryptographic protocol design

Année:

1986

Langue:

english

Fichier:

PDF, 1.67 MB

english, 1986

Non-commutative circuits and the sum-of-squares problem

Hrubeš, Pavel, Wigderson, Avi, Yehudayoff, Amir

Journal:

Journal of the American Mathematical Society

Année:

2011

Langue:

english

Fichier:

PDF, 370 KB

english, 2011

[ACM Press the twenty-eighth annual ACM symposium - Philadelphia, Pennsylvania, United States (1996.05.22-1996.05.24)] Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 - Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs

Babai, László, Gál, Anna, Kollár, János, Rónyai, Lajos, Szabó, Tibor, Wigderson, Avi

Année:

1996

Langue:

english

Fichier:

PDF, 978 KB

english, 1996

[ACM Press the 5th conference - Princeton, New Jersey, USA (2014.01.12-2014.01.14)] Proceedings of the 5th conference on Innovations in theoretical computer science - ITCS '14 - Non-commutative arithmetic circuits with division

Hrubeš, Pavel, Wigderson, Avi

Année:

2014

Langue:

english

Fichier:

PDF, 593 KB

english, 2014

[ACM Press the thirty-sixth annual ACM symposium - Chicago, IL, USA (2004.06.13-2004.06.16)] Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 - Derandomizing homomorphism testing in general groups

Shpilka, Amir, Wigderson, Avi

Année:

2004

Langue:

english

Fichier:

PDF, 190 KB

english, 2004

Reed–Muller Codes for Random Erasures and Errors

Abbe, Emmanuel, Shpilka, Amir, Wigderson, Avi

Journal:

IEEE Transactions on Information Theory

Année:

2015

Langue:

english

Fichier:

PDF, 514 KB

english, 2015

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling

Garg, Ankit, Gurvits, Leonid, Oliveira, Rafael, Wigderson, Avi

Journal:

Geometric And Functional Analysis

Année:

2018

Langue:

english

Fichier:

PDF, 815 KB

english, 2018

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Meir, Or, Wigderson, Avi

Journal:

Année:

2019

Langue:

english

Fichier:

PDF, 473 KB

english, 2019

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Meir, Or, Wigderson, Avi

Journal:

Année:

2019

Fichier:

PDF, 473 KB

2019

Mathematics and Computation (A Theory Revolutionizing Technology and Science) || 9. Weak random sources and randomness extractors

Wigderson, Avi

Année:

2019

Langue:

english

Fichier:

PDF, 319 KB

english, 2019

Mathematics and Computation (A Theory Revolutionizing Technology and Science) || 5. Lower bounds, Boolean circuits, and attacks on P vs. NP

Wigderson, Avi

Année:

2019

Langue:

english

Fichier:

PDF, 401 KB

english, 2019

Mathematics and Computation (A Theory Revolutionizing Technology and Science) || 5. Lower bounds, Boolean circuits, and attacks on P vs. NP

Wigderson, Avi

Année:

2019

Fichier:

PDF, 401 KB

2019

Boolean complexity classes vs. their arithmetic analogs

Anna Gál, Avi Wigderson

Journal:

Oded Goldreich, Avi Wigderson

Année:

1996

Langue:

english

Fichier:

PDF, 719 KB

english, 1996

Tiny families of functions with random properties: A quality-size trade-off for hashing

Journal:

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson

Année:

1997

Langue:

english

Fichier:

PDF, 298 KB

english, 1997

On Data Structures and Asymmetric Communication Complexity

Journal:

Joseph Gil, William Steiger, Avi Wigderson

Année:

1998

Langue:

english

Fichier:

PDF, 424 KB

english, 1998

Geometric medians

Journal:

Discrete Mathematics

Année:

1992

Langue:

english

Fichier:

PDF, 1.03 MB

english, 1992

nω(log n) lower bounds on the size of depth-3 threshold cicuits with AND gates at the bottom

Alexander Razborov, Avi Wigderson

Journal:

Information Processing Letters

Année:

1993

Langue:

english

Fichier:

PDF, 338 KB

english, 1993

Universal traversal sequences for expander graphs

Shlomo Hoory, Avi Wigderson

Journal:

Information Processing Letters

Année:

1993

Langue:

english

Fichier:

PDF, 237 KB

english, 1993

A tradeoff between search and update time for the implicit dictionary problem

Allan Borodin, Faith E. Fich, Friedhelm Meyer Auf Der Heide, Eli Upfal, Avi Wigderson

Journal:

Theoretical Computer Science

Année:

1988

Langue:

english

Fichier:

PDF, 698 KB

english, 1988

In search of an easy witness: exponential time vs. probabilistic polynomial time

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

Journal:

Année:

2002

Langue:

english

Fichier:

PDF, 257 KB

english, 2002

Non-deterministic communication complexity with few witnesses

Mauricio Karchmer, Ilan Newman, Mike Saks, Avi Wigderson

Journal:

Noam Nisan, Avi Wigderson

Année:

1994

Langue:

english

Fichier:

PDF, 582 KB

english, 1994

Hardness vs randomness

Journal:

Johan Håstad, Avi Wigderson

Année:

1994

Langue:

english

Fichier:

PDF, 1.04 MB

english, 1994

Simple analysis of graph tests for linearity and PCP

Journal:

Noam Nisan, Avi Wigderson

Année:

2003

Langue:

english

Fichier:

PDF, 168 KB

english, 2003

On rank vs. communication complexity

Journal:

Combinatorica

Année:

1995

Langue:

english

Fichier:

PDF, 420 KB

english, 1995

Super-logarithmic depth lower bounds via the direct sum in communication complexity

Mauricio Karchmer, Ran Raz, Avi Wigderson

Journal:

Rafi Heiman, Avi Wigderson

Année:

1995

Langue:

english

Fichier:

PDF, 765 KB

english, 1995

Randomized vs. deterministic decision tree complexity for read-once Boolean functions

Journal:

Année:

1991

Langue:

english

Fichier:

PDF, 1.02 MB

english, 1991

BPPhas subexponential time simulations unlessEXPTIMEhas publishable proofs

Lźszló Babai, Lance Fortnow, Noam Nisan, Avi Wigderson

Journal: